package com.zyj.test.month1.day16;

import java.util.*;

/**
 * @author Yijia Zhang
 * @create 2024-06-05 21:01
 */
public class code0030 {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLen = words[0].length();
        int wordArrLen = words.length;
        if (wordArrLen * wordLen > s.length()) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < wordLen; i++) {
            //从位置i开始
            if (i + wordArrLen * wordLen > s.length()) {
                break;
            }

            int k = 0;
            Map<String, Integer> map = generateMap(words);
            int j = i;
            for (; j < i + wordArrLen * wordLen; j += wordLen) {
                String substring = s.substring(j, j + wordLen);
                if (map.containsKey(substring)) {
                    Integer get = map.get(substring);
                    if (get > 0) {
                        k++;
                    }
                    map.put(substring, get - 1);
                }
            }
            if (k == wordArrLen) {
                res.add(i);
            }
            int l = i;
            while (j + wordLen <= s.length()) {
                String substring = s.substring(l, l + wordLen);
                if (map.containsKey(substring)) {
                    Integer get = map.get(substring);
                    if (get >= 0) {
                        k--;
                    }
                    map.put(substring, get + 1);
                }
                substring = s.substring(j, j + wordLen);
                if (map.containsKey(substring)) {
                    Integer get = map.get(substring);
                    if (get > 0) {
                        k++;
                    }
                    map.put(substring, get - 1);
                }
                l += wordLen;
                j += wordLen;
                if (k == wordArrLen) {
                    res.add(l);
                }
            }

        }
        return res;
    }

    public Map<String, Integer> generateMap(String[] words) {
        Map<String, Integer> map = new HashMap<>(words.length);
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        return map;
    }

}
